#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
#define endl '\n'

LL gcd(LL a, LL b)
{
	return b == 0 ? a : gcd(b, a % b);
}

bool vaild(LL t, LL x, LL y)
{
	int l = 1, r = 1e9;
	while(l < r)
	{
		LL mid = (l + r) >> 1;
		if(t * mid <= x) l = mid + 1;
		else r = mid;
	}
	if(l * t >= y) return false;
	return true;
	
}

void solve() 
{
    LL x, y; cin >> x >> y;
	vector<LL> a, b;
	for(int i = 1; i <= x / i; i++)
	{
		if(x % i == 0) 
		{
			a.push_back(i);
			if(x / i != i) a.push_back(x / i);
		}
	}
	for(int i = 1; i <= y / i; i++)
	{
		if(y % i == 0) 
		{
			b.push_back(i);
			if(y / i != i) b.push_back(y / i);
		}
	}
	// for(auto x : b) cout << x << " ";
	LL ans = 0;
	for(int i = 0; i < a.size(); i++)
	{
		for(int j = 0; j < b.size(); j++)
		{
			LL t = a[i] * b[j] / gcd(a[i], b[j]);
			LL p = y / t * t;
			if(p == y) p -= t;
			if(p > x)
			{
				// cout << a[i] << " " << b[j] << endl;
				ans = max(ans, a[i] + b[j]);
			}
		}
	}
	cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
	cin >> T;
	while(T--)
	{
        solve();
	}
	return 0;
}